package demo4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class SubsetSum {
    private int[] S;  // 输入集合 S
    private int[] x;  // 解向量，x[i]=1 表示 S[i] 在子集中，0 表示不在
    private int n;    // 集合大小
    private int M;    // 目标和
    private boolean hasSolution; // 是否找到解

    public SubsetSum(int[] S, int M) {
        this.S = S;
        this.n = S.length;
        this.M = M;
        this.x = new int[n];
        this.hasSolution = false;
    }

    // 回溯法求解
    private void backtrack(int k, int currentSum) {
        if (currentSum == M) {
            hasSolution = true;
            System.out.print("找到一个子集合: { ");
            for (int i = 0; i < n; i++) {
                if (x[i] == 1) {
                    System.out.print(S[i] + " ");
                }
            }
            System.out.println("}");
            return;
        }
        if (k >= n || currentSum > M) {
            return; // 剪枝：超出范围或和已大于 M
        }

        // 选择 S[k]
        x[k] = 1;
        backtrack(k + 1, currentSum + S[k]);

        // 不选择 S[k]
        x[k] = 0;
        backtrack(k + 1, currentSum);
    }

    public void solve() {
        System.out.println("正在求解子集合和问题...");
        System.out.println("输入集合 S = " + arrayToString(S));
        System.out.println("目标和 M = " + M);
        backtrack(0, 0);
        if (!hasSolution) {
            System.out.println("无解");
        }
    }

    // 辅助方法：将数组转换为字符串
    private String arrayToString(int[] arr) {
        StringBuilder sb = new StringBuilder("{ ");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) {
                sb.append(", ");
            }
        }
        sb.append(" }");
        return sb.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入集合大小
        System.out.print("请输入集合 S 的大小 n: ");
        int n = scanner.nextInt();

        // 输入集合元素
        int[] S = new int[n];
        System.out.println("请输入集合 S 的 " + n + " 个正整数：");
        for (int i = 0; i < n; i++) {
            S[i] = scanner.nextInt();
        }

        // 输入目标和
        System.out.print("请输入目标和 M: ");
        int M = scanner.nextInt();

        SubsetSum subsetSum = new SubsetSum(S, M);
        subsetSum.solve();
        scanner.close();
    }
}